#include <stdio.h>
#include <stdlib.h>

void merge_sort(int *a, int low, int high);
void merge(int * a, int low, int mid, int high);
int binarysearch(int a[], int x, int low, int high);
int find(int a[], int n, int x);
int find2(int a[], int n, int x);
int find3(int a[], int n, int x);

int main(void)
{
	int res;
	int a[7] = {2, 4, 5, 7, 14, 16, 19};

	res = find3(a, 7, 21);

	printf("%d\n", res);
	return 0;
}

//数组a 元素个数n  两数之和x
int find(int a[], int n, int x)
{
	int i, j;

	for (i = 0; i < n; ++i)
	{
		for (j = i; j < n; ++j)
		{
			if (a[i] + a[j] == x)
				return 1;
		}
	}
	return 0;
}

//数组a 元素个数n  两数之和x
int find2(int a[], int n, int x)
{
	int i;

	//归并排序 用时O(nlogn)
	merge_sort(a, 0, n);

	for (i = 0; i < n; ++i)
	{
		if (binarysearch(a, x-a[i], i, n) != -1)
			return 1;
	}
	return 0;
}

void merge_sort(int *a, int low, int high)
{
	int mid;
	if (high - low < 2) return; //递归基 该序列只有一个元素 是有序的
	mid = (low + high) / 2;

	merge_sort(a, low, mid);	//左半部分排序
	merge_sort(a, mid, high);	//右半部分排序

	merge(a, low, mid, high);	//合并俩个排好序的序列
}

void merge(int * a, int low, int mid, int high)
{
	int i, j, k;
	int * result = &a[low];	//result数组为最后结果
	int left_length = mid - low;
	int * left = (int *)malloc(sizeof(int) * left_length);
	int right_length = high - mid;
	int * right = &a[mid];

	for (i = 0; i < left_length; left[i] = result[i], ++i);//左半部分备份到left数组

	for (i = 0, j = 0, k = 0; j < left_length; )
	{
		if (k < right_length && right[k] < left[j]) result[i++] = right[k++];
		if (right_length <= k || left[j] <= right[k]) result[i++] = left[j++];
	}
	free(left);
}
int binarysearch(int a[], int x, int low, int high)
{
	int mid;
	while (low < high)
	{
		mid = (low + high) / 2;
		if (x < a[mid])
			high = mid;
		else if (a[mid] < x)
			low = mid + 1;
		else
			return mid;
	}
	return -1;
}

//数组a 元素个数n  两数之和x
int find3(int a[], int n, int x)
{
	int i, j;
	merge_sort(a, 0, n);

	i = 0;
	j = n-1;

	while (i <= j)
	{
		if (a[i] + a[j] == x)
			return 1;
		else if (a[i] + a[j] < x)
			++i;
		else
			--j;
	}

	return 0;
}